package com.github.yangyishe.p100;

/**
 * 6. N 字形变换
 * https://leetcode.cn/problems/zigzag-conversion/?envType=study-plan-v2&envId=top-interview-150
 * <p>
 * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
 * <p>
 * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
 * <p>
 * P   A   H   N
 * A P L S I I G
 * Y   I   R
 * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
 * <p>
 * 请你实现这个将字符串进行指定行数变换的函数：
 * <p>
 * string convert(string s, int numRows);
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "PAYPALISHIRING", numRows = 3
 * 输出："PAHNAPLSIIGYIR"
 * 示例 2：
 * 输入：s = "PAYPALISHIRING", numRows = 4
 * 输出："PINALSIGYAHRPI"
 * 解释：
 * P     I    N
 * A   L S  I G
 * Y A   H R
 * P     I
 * 示例 3：
 * <p>
 * 输入：s = "A", numRows = 1
 * 输出："A"
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 1000
 * s 由英文字母（小写和大写）、',' 和 '.' 组成
 * 1 <= numRows <= 1000
 */
public class Problem06 {
    public static void main(String[] args) {
        String s = "AB";

        Problem06 problem6 = new Problem06();
        String convert = problem6.convert(s, 2);
        System.out.println(convert);


    }

    /**
     * 思路(当n>=2时可用以下思路)
     * N字形变换, 可理解为将原数组, 按照2n-2一组, 分割成若干组数据
     * 然后逐次对这些数据进行相同位置的扫描n轮, 构建新数组
     * <p>
     * 每组扫描的特点(暂不考虑最后一组的情况): 举例时以n=4为例.
     * 1. 第1轮, 总是只扫描第1个 each[0]
     * 2. 第2轮到第n-2轮(如果有的话), 假定是第i+1轮, 分别扫描第i+1个和第2n-1-i个: each[i] each[2n-2-i], 如第2轮(i=1), 扫描第2个和第6个
     * 3. 第n-1轮, 只扫描第n个. each[n-1]
     * <p>
     * 扫描最后一组时, 如果最后一组的数量是m (m<=2n-2)
     * 当扫描下标>=m时, 就直接跳过扫描下一个
     *
     * @param s
     * @param numRows
     * @return
     */
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        // 每轮数量
        int eachCircleCount = 2 * numRows - 2;
        // 轮数
        int circleCount = (s.length() - 1) / eachCircleCount + 1;
        // 最后一轮数量
        int lastCircleCount = s.length() % eachCircleCount;
        lastCircleCount=lastCircleCount!=0?lastCircleCount:eachCircleCount;

        // 结果集
        char[] chars = new char[s.length()];
        int resultIndex = 0;

        for (int i = 0; i < numRows; i++) {
            for (int cir = 0; cir < circleCount; cir++) {
                int startIndex = cir * eachCircleCount;
                if (i == 0) {
                    chars[resultIndex++] = s.charAt(startIndex);
                } else if (i < numRows - 1) {
                    if (cir!=circleCount-1||i < lastCircleCount) {
                        chars[resultIndex++] = s.charAt(startIndex + i);
                    }
                    if (cir!=circleCount-1||2 * numRows - 2 - i < lastCircleCount) {
                        chars[resultIndex++] = s.charAt(startIndex + 2 * numRows - 2 - i);
                    }
                } else {
                    if (cir!=circleCount-1||i < lastCircleCount) {
                        chars[resultIndex++] = s.charAt(startIndex + i);
                    }
                }
            }
        }

        return String.valueOf(chars);
    }
}
